/*
	hash.cc		Transposition Hash Table
	Copyright (c) 2000, 2001, 2002, 2004 Kriang Lerdsuwanakij
	email:		lerdsuwa@users.sourceforge.net

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include "hash.h"
#include "iter.h"

#include <cstring>
#include <iostream>

// Initialize hash_pos_table in readable form.
// Computation efficient one will be calculated in trans_table_init().
// Assume at least 32-bit int.
unsigned int	hash_pos_table[64] = {
	 0,  1,  2,  3,  4,  5,  6, 15,
	 1,  7,  8,  9, 10, 11, 12,  6,
	 2,  8, 12, 13, 14,  7, 11,  5,
	 3,  9, 13, 15,  0, 14, 10,  4,
	 4, 10, 14,  0, 15, 13,  9,  3,
	 5, 11,  7, 14, 13, 12,  8,  2,
	 6, 12, 11, 10,  9,  8,  7,  1,
	15,  6,  5,  4,  3,  2,  1,  0
};

trans_board *trans_used_table[NUM_MOVE][NUM_HASH];
trans_board *trans_tail_table[NUM_MOVE][NUM_HASH];
trans_board *trans_free_list;

/* Initialize variables required for proper transposition table operations. */
void	trans_table_init()
{
					// Initialize computation efficient
					// version of hash_pos_table.
	for (int i = 0; i < 64; ++i)
		hash_pos_table[i] = 1 << hash_pos_table[i];

					// Empty trans_used_table.
	for (int i = 0; i < NUM_MOVE; ++i)
		for (int j = 0; j < NUM_HASH; ++j)
			trans_used_table[i][j] = 0;

					// Allocate nodes for hash table.
	for (int i = 0; i < NUM_TRANS_BOARD; ++i) {
		trans_board *t = new trans_board;
		t->next = trans_free_list;
		trans_free_list = t;
	}
}

/* Compute hash from entire board.  */
int	get_hash(byte_board_info *board)
{
	int hash = 0;
	board_iterator	iter;
	iter.init_pos();
	do {
		hash ^= get_hash_piece(board->board[iter.pos], iter.pos);
	} while (iter.next());
	return hash;
}

/* Compute hash from entire board.  */
#if 0
int	get_hash(bit_byte_board_info * /*board*/)
{
	throw 0;	// Not implemented
	return 0;
}
#endif

int	max_hash_move = 50;
int	hash_hit = 0;
int	hash_miss = 0;

void	set_max_hash_move(int move)
{
	max_hash_move = move;
}

void	free_hash_move(int move)
{
	for (int i = 0; i < NUM_HASH; ++i) {
		trans_board *front = trans_used_table[move][i];
		if (front) {
						// Move entire list to free list
			trans_tail_table[move][i]->next = trans_free_list;
			trans_free_list = trans_used_table[move][i];
			trans_used_table[move][i] = 0;
		}
	}
}

void free_hash_all_move()
{
	for (int i = 0; i < NUM_MOVE; ++i)
		free_hash_move(i);
}

trans_board *get_hash_board(byte_board_info *board, int player)
{
	int	move = board->get_num_move();
	if (move > max_hash_move)		// It's wasteful to hash moves
						// that are too deep.  Benefit
						// from tree pruning is small.
		return 0;

	int	hash = board->hash;
	int	hash_index = hash % (NUM_HASH-1);
	trans_board *t = trans_used_table[move][hash_index];
	while (t) {
		if (t->board.hash == hash
		    && !memcmp(t->board.board, board->board, sizeof(byte_board_type))
		    && (t->player == player)) {
			hash_hit++;
			return t;
		}
		t = t->next;
	}

	hash_miss++;
	t = get_temp_board(board);
	t->next = trans_used_table[move][hash_index];

						// Empty list
						// Also record tail of list
	if (!trans_used_table[move][hash_index])
		trans_tail_table[move][hash_index] = t;

	trans_used_table[move][hash_index] = t;

	t->score = INVALID_SCORE;
	t->player = player;
	return t;
}

trans_board *get_temp_board(byte_board_info *board)
{
	while (!trans_free_list) {
		free_hash_move(max_hash_move);
		max_hash_move--;
	}

	trans_board *t = trans_free_list;
	trans_free_list = t->next;
	t->board = *board;
	return t;
}

#define	NUM_HASH_COUNT	30

void	get_hash_info(int move)
{
	int	count[NUM_HASH_COUNT];
	for (int i = 0; i < NUM_HASH_COUNT; ++i)
		count[i] = 0;
	
	for (int i = 0; i < NUM_HASH; ++i) {
		trans_board *t = trans_used_table[move][i];
		int	cur_count = 0;
		while (t) {
			t = t->next;
			cur_count++;
		}
		if (cur_count >= NUM_HASH_COUNT)
			count[NUM_HASH_COUNT-1]++;
		else
			count[cur_count]++;
	}
	std::cout << '[';
	for (int i = 0; i < NUM_HASH_COUNT; ++i)
		std::cout << ' ' << count[i];
	std::cout << " ]";
	int sum = 0;
	for (int i = 0; i < NUM_HASH_COUNT; ++i)
		sum += count[i];
	std::cout << ' ' << sum << "\n";
}

